package array;

import java.util.Arrays;

import org.junit.Test;

import utils.ArrayGenerator;

public class Ex283 {
    class Solution {
        //导致位置改变，错误
        public void moveZeroesX(int[] nums) {
             int lo = 0, hi = nums.length - 1;
             while (lo < hi) {
                 while (nums[hi] == 0 && hi > lo) hi--; //hi到达最后第一个非零位置
                 while (nums[lo] != 0 && hi > lo) lo++; //lo到达左边第一个0
                 //交换
                 int temp = nums[lo];
                 nums[lo] = nums[hi];
                 nums[hi] = temp;
             }
        }

        //将非0元素直接从前往后一个一个搬到最前面【标记压缩】
        public void moveZeroes1(int[] nums) {
            int zeros = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 0) zeros++;
            }
            int idx = 0; //nums.length - zeros - 1
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != 0) {
                    int temp = nums[i];
                    nums[i] = nums[idx];
                    nums[idx] = temp;
                    idx++;
                }              
                if (idx == nums.length - zeros) break;
            }
         }

         public void moveZeroes2(int[] nums) {
             int hi = 0, lo = 0;
             while (hi < nums.length) {
                 while (lo < nums.length && nums[lo] != 0) lo++; //lo为最左0
                 if (hi < lo) {
                     //第一次遍历是，hi还没走
                     hi = lo + 1;
                 }
                 while (hi < nums.length && nums[hi] == 0) hi++; //hi为lo后第一个非0数
                 if (hi == nums.length || lo == nums.length) break;
                 //交换
                 int temp = nums[lo];
                 nums[lo] = nums[hi];
                 nums[hi] = temp;
             }
         }
         //对方法2进行优化
         //找到右边第一个不为0的元素与前面的0交换
         public void moveZeroes(int[] nums) {
            int hi = 0, lo = 0;
            for (; hi < nums.length; hi++) {
                if (nums[lo] != 0 && nums[hi] != 0) {
                    lo++; //lo,hi全不为0，继续右移
                } else if (nums[lo] == 0 && nums[hi] == 0) {
                    continue;
                } else if (nums[lo] == 0 && nums[hi] != 0) {
                     //交换
                    int temp = nums[lo];
                    nums[lo] = nums[hi];
                    nums[hi] = temp;
                    lo++;
                }
            }
        }
        
    }

   
    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = ArrayGenerator.getArray(100, 100);
        s.moveZeroes(nums);
        System.out.println(Arrays.toString(nums));
    }
}
